package dp;
// 钢条切分 动态规划 问咋样切割得到的价值最大

import java.util.Arrays;

public class CutRodProblem {
    public static void main(String[] args) {
        //前面数组分别对应1,2,3,4....对应的价值 最后是要切分的数值
        cut(new int[]{0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30}, 10);
    }

    private static void cut(int[] num, int n) {
        int[][] dp = new int[num.length][n + 1];
        for (int i = 1; i < num.length; i++) {
            for (int j = 1; j < n + 1; j++) {
                if (j >= i) { //放得下
                    dp[i][j] = Integer.max(dp[i - 1][j], num[i] + dp[i][j - i]);
                } else {//放不下
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        print(dp);
    }

    private static void print(int[][] dp) {
        System.out.println("=====");
        for (int[] ints : dp) {
            System.out.println(Arrays.toString(ints));
        }
        System.out.println("=====");
    }
}
